package com.example.leetcode.prcatice;

import java.util.*;

/**
 * 对于某些非负整数 k ，如果交换 s1 中两个字母的位置恰好 k 次，能够使结果字符串等于 s2 ，则认为字符串 s1 和 s2 的 相似度为 k 。
 *
 * 给你两个字母异位词 s1 和 s2 ，返回 s1 和 s2 的相似度 k 的最小值。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/k-similar-strings
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Test854 {

    int result = Integer.MAX_VALUE;
    String t;

    public int kSimilarity(String s1, String s2) {
       // return dfs(s1.toCharArray(),s2.toCharArray(),0,0);
        if (s1.equals(s2)){
            return 0;
        }
        t =s2;
        int n = s1.length();
        Map<String,Integer> map = new HashMap<>();
        PriorityQueue<String> queue = new PriorityQueue<>((x,y) ->{
            Integer xValue = map.get(x);
            Integer yValue = map.get(y);
            return (f(x) + xValue) - (f(y) + yValue);
        });
        map.put(s1,0);
        queue.add(s1);
        while (!queue.isEmpty()) {
            String poll = queue.poll();
            int step = map.get(poll);
            char[] chars = poll.toCharArray();
            int idx = 0;
            while (idx < n && chars[idx] == t.charAt(idx)){
                idx++;
            }
            for (int i = idx + 1;i<n;i++) {
                if (chars[i] != t.charAt(idx) || chars[i] == t.charAt(i)) {
                    continue;
                }
                swap(chars,idx,i);
                String change = String.copyValueOf(chars);
                // 回溯
                swap(chars,idx,i);
                if (map.containsKey(change) && map.get(change) <= step + 1){
                    continue;
                }
                if (Objects.equals(t,change)) {
                    return step + 1;
                }
                map.put(change,step +1);
                queue.add(change);
            }
        }
        return -1;
    }


    int f(String s) {
        int ans = 0;
        for (int i = 0;i<s.length();i++){
            if (s.charAt(i) != t.charAt(i)) {
                ans++;
            }
        }
        return ans + 1 >> 1;
    }


    private int dfs(char[] c1,char[] c2,int start,int cur) {
        if (cur >= result) {
            return result;
        }

        if (start == c1.length -1){
            return result = Math.min(cur,result);
        }

        for (int i = start;i<c1.length;i++){
            if (c1[i] != c2[i]) {
                for (int j = i + 1; j<c2.length;j++) {
                    if (c2[j] == c1[i] && c2[j] != c1[j]) {
                        swap(c2,i,j);
                        dfs(c1,c2,i+ 1,cur+1);
                        // 回溯
                        swap(c2,i,j);
                        if (c2[i] == c1[j]) {
                            break;
                        }
                    }
                }
                return result;
            }
        }
        return result = Math.min(result,cur);
    }


    private void swap(char[] cs ,int source,int target) {
        char t =  cs[target];
        cs[target] = cs[source];
        cs[source] = t;
    }

}
